package arithmetic.leetCode;

/**
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * @author dycong
 * @date 2019/12/3 9:23
 */
public class FindMedianSortedArrays_4 {
    public static void main(String[] args) {
        FindMedianSortedArrays_4 findMedianSortedArrays_4 = new FindMedianSortedArrays_4();
        int[] nums1 = {1,2};
        int[] nums2 = {3,4};
        System.out.println(findMedianSortedArrays_4.findMedianSortedArrays(nums1, nums2));
        System.out.println(findMedianSortedArrays_4.findMedianSortedArrays_i(nums1, nums2));
    }

    /*
     * 1.首先，让我们在任一位置 i 将 A(长度为m) 划分成两个部分：
     *            leftA            |                rightA
     *   A[0],A[1],...      A[i-1] |  A[i],A[i+1],...A[m - 1]
     *
     * 由于A有m个元素，所以有m + 1中划分方式(i = 0 ~ m)
     *
     * 我们知道len(leftA) = i, len(rightA) = m - i;
     * 注意：当i = 0时，leftA是空集，而当i = m时，rightA为空集。
     *
     * 2.采用同样的方式，将B也划分为两部分：
     *            leftB            |                rightB
     *   B[0],B[1],...      B[j-1] |   B[j],B[j+1],...B[n - 1]
     *  我们知道len(leftA) = j, len(rightA) = n - j;
     *
     *  将leftA和leftB放入一个集合，将rightA和rightB放入一个集合。再把这两个集合分别命名为leftPart和rightPart。
     *
     *            leftPart         |                rightPart
     *   A[0],A[1],...      A[i-1] |  A[i],A[i+1],...A[m - 1]
     *   B[0],B[1],...      B[j-1] |  B[j],B[j+1],...B[n - 1]
     *
     *   如果我们可以确认：
     * todo 1.len(leftPart) = len(rightPart); =====> 该条件在m+n为奇数时，该推理不成立
     *      2.max(leftPart) <= min(rightPart);
     *
     *   median = (max(leftPart) + min(rightPart)) / 2;  目标结果
     *
     *   要确保这两个条件满足：
     *todo   1.i + j = m - i + n - j(或m - i + n - j + 1)  如果n >= m。只需要使i = 0 ~ m，j = (m+n+1)/2-i =====> 该条件在m+n为奇数/偶数时，该推理都成立
     *       2.B[j] >= A[i-1] 并且 A[i] >= B[j-1]
     *
     *   注意:
     *todo   1.临界条件：i=0,j=0,i=m,j=n。需要考虑
     *       2.为什么n >= m ? 由于0 <= i <= m且j = (m+n+1)/2-i,必须确保j不能为负数。
     *
     *   按照以下步骤进行二叉树搜索
     * todo  1.设imin = 0,imax = m，然后开始在[imin,imax]中进行搜索
     *       2.令i = (imin+imax) / 2, j = (m+n+1)/2-i
     *       3.现在我们有len(leftPart) = len(rightPart)。而我们只会遇到三种情况：
     *
     *todo  ①.B[j] >= A[i-1] 并且 A[i] >= B[j-1]  满足条件
     *      ②.B[j-1] > A[i]。此时应该把i增大。 即imin = i + 1;
     *      ③.A[i-1] > B[j]。此时应该把i减小。 即imax = i - 1;
     *
     * */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) { // to ensure m<=n
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && nums2[j - 1] > nums1[i]) {
                iMin = i + 1; // i is too small
            } else if (i > iMin && nums1[i - 1] > nums2[j]) {
                iMax = i - 1; // i is too big
            } else { // i is perfect
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums2[j], nums1[i]);
                }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }


    public double findMedianSortedArrays_i(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m >= n) {
            int[] ints = nums2;
            nums2 = nums1;
            nums1 = ints;
            int tmp = m;
            m = n;
            n = tmp;
        }
        int iMin = 0, iMax = m;
        int halfLen = (m + n + 1) / 2;

        while (iMax >= iMin) {
            int i = (iMax + iMin) / 2;
            int j = halfLen - i;
            if (i > iMin && nums1[i - 1] > nums2[j]) {
                //i--;
                iMax = i - 1;
            } else if (i < iMax && nums2[j - 1] > nums1[i]) {
                //j--
                iMin = i + 1;
            } else {
                int maxLeft;
                if (i == 0) {
                    maxLeft = nums2[halfLen - 1];
                    //i=m-1不能证明j=0;
                } else if (j == 0) {
                    maxLeft = nums1[halfLen - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    //奇数
                    return maxLeft;
                }

                int minRight;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                //必须提前声明为 double 类型
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0D;
    }
}
